package com.zhao.utils;

import java.math.BigDecimal;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import org.springframework.beans.factory.annotation.Autowired;

import com.zhao.po.OptimalPath;
import com.zhao.po.Route;
import com.zhao.service.RouteService;

/**
 * 这里是计算出最短路径的算法的类： 这个类需要穿个参数来初始化才能算出最短路径，所以常规的做成工具类不可行
 * 
 * @author Administrator
 *
 */
public class MyWeightedGraph {

	@Autowired
	private RouteService routeService;

	// 定义一些静态的常量
	public static String LENGTH = "length";
	public static String COST = "cost";
	public static String TIME = "time";

	private class Vertex implements Comparable<Vertex> {
		private String vertexLabel;// 顶点标识
		private List<Edge> adjEdges;// 顶点的所有邻接边(点)
		private int dist;// 顶点到源点的最短距离
		private Vertex preNode;// 前驱顶点

		public Vertex(String vertexLabel) {
			this.vertexLabel = vertexLabel;
			adjEdges = new LinkedList<Edge>();
			dist = Integer.MAX_VALUE;
			preNode = null;
		}

		@Override
		public int compareTo(Vertex v) {
			if (this.dist > v.dist)
				return 1;
			else if (this.dist < v.dist)
				return -1;
			return 0;
		}
	}

	private class Edge {
		private int weight;// 边的权值(带权图)
		private Vertex endVertex;

		public Edge(int weight, Vertex endVertex) {
			this.weight = weight;
			this.endVertex = endVertex;
		}
	}

	private Map<String, Vertex> weightedGraph;// 存储图(各个顶点)
	private Vertex startVertex;// 单源最短路径的起始顶点
	private Vertex endVertex;// 单源最短路径的起始顶点
	private StringBuilder sb = new StringBuilder();

	/**
	 * 这里构建图传入两个参数：
	 * 
	 * @param roadLines
	 *            构建图要传递的路劲信息
	 * @param weight
	 *            我们要比较的权重,这里先暂时设计为以路径为权重
	 */
	public MyWeightedGraph(List<Route> roadLines, String weight) {
		// TODO Auto-generated constructor stub
		weightedGraph = new LinkedHashMap<String, MyWeightedGraph.Vertex>();
		buildGraph(roadLines, weight);// 解析字符串构造图
	}

	private void buildGraph(List<Route> roadLines, String myweight) {
		String startNodeLabel, endNodeLabel;
		Vertex startNode, endNode;
		int weight;
		String method = "getRoute" + myweight;

		for (Route roadLine : roadLines) {
			startNodeLabel = String.valueOf(roadLine.getStartid());
			endNodeLabel = String.valueOf(roadLine.getEndid());
			weight = Integer.valueOf(ReflectUtil.execute(roadLine, method).toString());

			endNode = weightedGraph.get(endNodeLabel);
			if (endNode == null) {
				endNode = new Vertex(endNodeLabel);
				weightedGraph.put(endNodeLabel, endNode);
			}

			startNode = weightedGraph.get(startNodeLabel);
			if (startNode == null) {
				startNode = new Vertex(startNodeLabel);
				weightedGraph.put(startNodeLabel, startNode);
			}
			Edge e = new Edge(weight, endNode);
			// 对于无向图而言,起点和终点都要添加边
			// endNode.adjEdges.add(e);
			startNode.adjEdges.add(e);
		}

	}

	private void dijkstra() {
		BinaryHeap<Vertex> heap = new BinaryHeap<MyWeightedGraph.Vertex>();
		init(heap);// inital heap

		while (!heap.isEmpty()) {
			Vertex v = heap.deleteMin();
			List<Edge> adjEdges = v.adjEdges;// 获取v的所有邻接点
			for (Edge e : adjEdges) {
				Vertex adjNode = e.endVertex;
				// update
				if (adjNode.dist > e.weight + v.dist) {
					adjNode.dist = e.weight + v.dist;
					adjNode.preNode = v;
				}
			} // end for

			// 更新之后破坏了堆序性质,需要进行堆调整,这里直接重新构造堆(相当于decreaseKey)
			heap.buildHeap();
		}

	}

	private void init(BinaryHeap<Vertex> heap) {
		startVertex.dist = 0;// 源点到其自身的距离为0
		for (Vertex v : weightedGraph.values()) {
			heap.insert(v);
		}
	}

	public void showDistance() {
		for (Vertex v : weightedGraph.values()) {
			addPath(v);
			System.out.println();
			System.out.println("顶点 " + v.vertexLabel + "到源点" + startVertex.vertexLabel + " 的距离: " + v.dist);
		}
	}

	// 添加路径点
	private void addPath(Vertex end) {
		if (end.preNode != null)
			addPath(end.preNode);
		sb.append(end.vertexLabel + "-");
	}

	// ============下面是为了更加的适应我们项目需求而修改的方法
	// public StepResult getMinStep(int start, int end) {
	// StepResult step=new StepResult();
	// if (weightedGraph != null) {
	// // 设置起始点
	// startVertex = weightedGraph.get(String.valueOf(start));
	// endVertex = weightedGraph.get(String.valueOf(end));
	//
	// dijkstra();
	// addPath(endVertex);
	// System.out.println();
	// }
	// step.setMinstep(sb.toString().substring(0, sb.toString().length()-1));
	// step.setLength(endVertex.dist);
	// return step;
	// }

	/**
	 * 改进的获取最短路径的方法
	 * 
	 * @param start
	 * @param end
	 * @return
	 */
	public OptimalPath getMinStep(int start, int end) {
		// 创建一个最短路径对象，并设置这个最短路径的一些信息
		OptimalPath step = null;
		if (weightedGraph != null) {
			step = new OptimalPath();
			// 设置起始点
			startVertex = weightedGraph.get(String.valueOf(start));
			endVertex = weightedGraph.get(String.valueOf(end));
			dijkstra();
			addPath(endVertex);

			String routeDetail = sb.toString().substring(0, sb.toString().length() - 1);
			String[] routes = routeDetail.split("-");
			step.setStartid(start);
			step.setEndid(end);
			step.setRoutedetail(routeDetail);

			// 根据这个信息来获取并设置这条最短路径的总运费和总耗时
			BigDecimal allCost = null;
			BigDecimal alllegth = null;
			Integer allTime = null;

			// 遍历两个点之间的信息，相加获取总和
			for (int i = 0; i < routes.length - 1; i++) {
				if (i == 0) {
					allCost = new BigDecimal("0");
					alllegth = new BigDecimal("0");
					allTime = 0;
				}
				Route route = routeService.getRouteByStartAndEnd(routes[i], routes[i + 1]);
				allCost.add(route.getRoutecost().multiply(BigDecimal.valueOf(route.getRoutetime())));
				allTime += route.getRoutetime();
				alllegth.add(route.getRoutelength());

			}

			step.setRoutelength(alllegth);
			step.setRoutecost(allCost);
			step.setRoutetime(allTime);

		}
		return step;
	}

}